Characterising the paths through a network is a basic capability that lies beneath routing, congestion control and provision of differentiated quality of service. Networks can be layered on top of other networks, but path characterisation is useful at any layer, whether the network consists of Ethernet switches, Internet Protocol (IP) routers, or general purpose computers arranged in what is often called an overlay network, such as a peer-to-peer network. In each case, a unicast path through a network is the sequence of forwarding nodes and links between a sending end-node and a receiving end-node. The path between any two end-nodes is determined by the routing system.
Characterisation of a network path involves taking some measure of the combined effect of all the forwarding nodes and links on the path. For instance, the propagation delay of a network path is the sum of all the propagation delays of each link. Similarly, the hop count of the path is the sum of how many nodes forward data on the path. Or the congestion along a path is the combination of the congestion at each node or link along the path. Congestion is typically defined as the probability of the offered load not being served, so the way to combine a number of congestion metrics into a congestion metric that characterises the path is to take the combinatorial probability of congestion at every node on the path.
Given there are a huge number of possible paths through a network, an efficient way to characterise any particular path is for the nodes on the path to solely characterise their local contribution to each path metric. Then, as they forward data, they combine their local contribution to the path metric into each unit of data as they forward it (whether frames or packets, etc). They must use the appropriate function for combining their local characterisation with the characterisation accumulated so far in the data being forwarded.
For instance, if the characterisation of propagation delay is required, a field in the header of each packet may be standardised in order to carry a value representing propagation delay. Then each node can add its local characterisation of propagation delay to the value arriving in the header and replace the result in the header as the new value to be forwarded to the next node. In this way each value in each data header accumulates the path's propagation delay as it traverses the path. Equivalently, each forwarding node could subtract rather than add its local characterisation from the value in each header. As long as the combining function chosen was standardised and appropriate, the headers of data packets would accumulate the characterisation of the path used by the data.
An appropriate combining function for congestion is that for combinatorial probability. For instance, if the value of congestion arriving at forwarding node j in a data header is hj, and the local characterisation of congestion is mj, then the node should forward data with the value of the combinatorial probability of both h(j+1)=1−(1−hj)(1−mj). This example illustrates that each characteristic of a network path must be combined into the header at each forwarding node using the combining function appropriate to the metric concerned.
The above general technique for characterising each path through a network only allows the receiving end-node to see the characterisation of the complete path. Stated more generally, the technique allows each node on the path to characterise the path traversed so far—its upstream path. However, frequent, timely path characterisation is most useful to the sending end-node, not the receiver. More generally a frequent, timely characterisation of the remaining downstream path would be much more useful to each forwarding node on the path than a characterisation of the upstream path already traversed. With frequent, timely information about the remaining path about to be traversed by each packet, the sending node, and each forwarding node would be able to make timely decisions to control how much data they sent and on which path.
A prior patent application filed by the present applicant and published as WO2005/096566 proposed that each sending end-node could arrange to initialise each path characterisation value in each data header so that, on average, after the same process of accumulating each forwarding node's local characterisation of the path, the value in each data header would end up at a known target value by the time it reached the receiver. The particular target value to aim for would need to be well-known and standardised everywhere, typically zero.
As a consequence of this initial value set by the sender, each data header arriving at each forwarding node would carry a value characterising its remaining downstream path, at least on average. The sender could determine the best initial value for each data header using feedback about the whole path from the receiving node. The sender will, in effect, be continuously declaring the expected characterisation of the path within the packet headers of the data it sends into the path. When a paper relating to this invention was subsequently published [Briscoe05a] the term “re-feedback” was coined for the process of re-inserting feedback from the receiver back into the forward data path.
Once each data packet carries the expected characterisation of its remaining path through the network, network forwarding nodes can use this information to control their operation. This network control might conflict with an individual sender's self-interest. For instance, if the header value characterises congestion on the downstream path, the network may wish to limit the rate that data can be sent into such a congested path by some pre-agreed formula. This is an example of a case where the individual's self-interest is at odds with the general good of other users of the network, so the network may wish to police the rate allowed for each user to meet some wider objective, such as fairness. Such a policing function was described in another patent application filed by the present applicant and having application number PCT/GB2006/000417. However, as soon as forwarding nodes try to use the information the individual sender gives them against the sender's own interests, it would seem likely that the individual sender will be tempted to falsify the information.
Some possible scenarios resulting from cheating are shown in FIG. 1. In the lower half of the figure, a sender S1 (labelled 10) is shown sending data to a receiver R1 (labelled 16) over a route through networks N1, N2 and N4 (labelled 11, 12 and 14 respectively) chosen from a wider selection of networks additionally including networks N3 and N5 (labelled 13 and 15 respectively) by the routing protocol. Aligned with this view of the path through the internetwork is a plot of downstream path congestion in one possible packet traversing the path. Alternatively, the same plots could represent the average of the path characterisation metrics in a flow of packets along the path. Of course, downstream congestion is just one possible path characterisation metric that could be illustrated.
It can be seen that, as the packet traverses the path of network elements 18, those that are congested reduce the path characterisation value in the packet's header by an amount associated with their local congestion. It will noted that there will usually be several network elements 18 within each network, but for simplicity only those at an entry or an exit point of each network are shown. Any of the network elements may have an associated step-change in the graph in the upper half of FIG. 1.
Five possible scenarios are illustrated in the upper part of the figure, labelled a-e. In scenario (a) the source initialises the header value correctly so that it arrives at the destination R1 set to the target value zero. In this case, at each point on the path the value in the header then correctly represents downstream congestion from that point to the destination. But in scenario (b), the source has not initialised the header value to a sufficiently high value, so it undershoots the target just before the destination, somewhere within network N4. Each subsequent scenario c-e shows the source initialising the header value to progressively lower values, so that in scenario (c) the packet becomes negative in network N2, in scenario (d) it becomes negative in network N1 and in scenario (e) it is negative when it is initialised, so it is never positive in any network.
A further patent application filed by the present applicant and published as WO2005/109783 proposed a function at the egress of a network to test whether the sender was indeed initialising header values so that, on average, they reached the agreed constant value at the destination, and to sanction any flows that appeared to be understating their path's characterisation, for instance by dropping a commensurate proportion of the data. We generally call these functions that test metric validity ‘dropping functions’ even though sanctions short of dropping may be chosen in practice, such as packet truncation or even triggering off-line sanctions such as invoking penalty clauses in contracts.
We collectively call the above policing functions and dropping functions ‘incentive mechanisms’, because it can be shown that sanctions against traffic not declaring truthful path metrics can be arranged so that the sender's most successful strategy will be to honestly declare the characterisation of the path. However, the sender will only adopt such an honest strategy if it is actually trying to send information to a receiver. But not all potential senders conform to this stereotype. There may be malicious parties who are willing to send traffic into the network merely to disrupt other people, irrespective of whether they have any useful information to send, or anyone to send it to. For senders with such malicious motives, there will be no incentive to declare the path metric honestly when sending such dummy traffic. Taking the congestion path metric as an example, such a malicious sender is likely to declare a very low or even zero level of congestion on the path, in order that any rate policer using the congestion information will allow it to send as fast as possible.
Such dummy data from a malicious sender may well be dropped at the egress of the network, or earlier, because its initially declared characterisation of path congestion will have been insufficient to remain above the target level once decremented along the path. However, it may well have still caused problems earlier in the network, before being dropped. It may be the sender's objective to cause problems within the network, rather than to reach a destination across the network. Embodiments of the present invention aim to prevent these problems.
We said that characterising the paths through a network is a basic capability that lies beneath routing, congestion control and provision of differentiated quality of service. Many of these uses of path characterisation take the sum of the characterisations of many paths over time. This is particularly so within a network and between networks, where aggregate traffic is handled, rather than single flows. The sum can be used to determine an average, or to determine the total effect that one network has on another.
However, any flows of traffic from dishonest senders will pollute such aggregate sums, because they do not truly reflect the characteristics of the downstream paths they claim to reflect.
Without loss of generality, we will make the following discussion more concrete by assuming that it has been arranged that a numerically higher path characterisation is treated less favourably by the network, and its target value is zero. Therefore, it will be in the interest of a malicious sender to understate the path characteristic, and such data will eventually undershoot the zero target somewhere within the network. Therefore we can say that the flows that are of concern are those for which the lifetime balance has become persistently negative. It may be that not all data packets in the flow carry negative values, but when all the header values of all the packets within such flows are considered as a whole, the sum effect is negative. We will call these ‘persistently negative flows’.
One particularly serious example of the damaging effect of persistently negative flows is the case where networks might agree to use the sum of path characterisations as the metric by which one network penalises the other if it has failed to deliver an agreed quality of service. Such a metric might further be used by one network to compare the qualities of routes through two different networks and from time to time to change its choice of routing to ensure it uses the best quality or cheapest downstream network. If the sum is polluted by persistently negative flows, the decisions made based on the sum may be incorrect. Indeed, it may even be in a malicious network's interest to create dummy traffic in order to pollute the sum, so that a neighbouring network makes a decision to the malicious network's advantage.
A specific example of this problem is where the characterisations of downstream congestion are summed together in all traffic crossing the border between two networks. This sum should represent the penalty that the upstream network should be made to suffer for all the congestion it has allowed its users to cause in downstream networks. Two networks might agree that the upstream network should keep this sum below a certain threshold, or perhaps multiple thresholds will be set, each with an increasing penalty if they are exceeded. Or, more generally, the upstream network may agree to pay the downstream network a charge proportional to the sum. In all these cases, the penalty will be understated if persistently negative flows are included in the sum. And if the penalty is understated, the upstream network may be encouraged to continue to allow malicious senders to understate congestion path metrics. Or indeed, the upstream network may be encouraged to create its own dummy traffic with persistently negative header values and send it into a neighbouring network to reduce the overall sum used to determine penalties it must suffer, by offsetting the positive values in other flows with the negative values in its dummy traffic.